/*
 * VM.h defines functions of VMs
 * it build a VM table using VM matrix
 * divide the VMs into groups with an 
 * i-partition. 
 * VMs are assigned to hosts randomly 
 * at the beginning, and the vm place-
 * ment was written to file in order to
 * be used by the routing program.
*/

#ifndef VM_H
#define VM_H

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <map>
#include <list>
#include <vector>
#include <algorithm>
#include <time.h>
#include "Routing_topology.h"

using namespace std;

struct nearest
{
	double value;
	double ratio;
	int level;
	int leveli;
	bool marked;
	nearest()
	{
		marked = false;
	}
	bool operator <(nearest j)
	{
		bool res = (this->ratio < j.ratio);
		return res;
	}
	bool operator >(nearest j)
	{
		bool res = (this->ratio > j.ratio);
		return res;
	}
	bool operator ==(nearest j)
	{
		bool res = (this->ratio == j.ratio);
		return res;
	}
	bool operator <=(nearest j)
	{
		bool res = (this->ratio <= j.ratio);
		return res;
	}
	bool operator >=(nearest j)
	{
		bool res = (this->ratio >= j.ratio);
		return res;
	}
};

struct ptree_cord
{
	int level;
	int i;
};

class VMTable
{
private:
	struct node
	{
		vector<int> cluster;
		node *parent;
		int center;
		double min_aver;
		int n;
		node()
		{
			min_aver = 9999;
		}
	};
	int i_partition;
	map<int, VM> vms;
	map<int, node*> leafvms;
	map<int, vHost> hosts;
	//map<string, double> flow;//for vms
	vector<vector<double> > flow;
	map<string, double> utility;
	map<string, double> capacity;
	vector<vector<double> > distance;//distance between hosts
	Routing_topo *topo;
	map<int, bool> ishost;
	map<int, bool> centered;
	vector<vector<node*> > ptree;//ptree[i][j], j-th node in i-th level, bottom level: 0
	vector<int> vmlist;
	vector<double> clusterFlow;
	int totalSlots;
	bool treeBuilt;
	const static int maxVMsize = 10000;
	double limiter;
	int adi, adj;
	int preadi, preadj;
	int ref_i;
	int vmwp_ref;
	map<string, bool> moved;
	map<string, bool> focus;
	vector<nearest> i_max;
	map<string, bool> i_focus;
	map<int, bool> ipfocus;
	int swap_limit;
public:
	int cluster_cover;
	bool success;
	VMTable()
	{
		ipfocus.clear();
		vms.clear();
		hosts.clear();
		flow.clear();
		ishost.clear();
		leafvms.clear();
		utility.clear();
		vmlist.clear();
		centered.clear();
		focus.clear();
		i_max.clear();
		i_focus.clear();
		topo = NULL;
		totalSlots = 0;
		treeBuilt = false;
		i_partition = -1;
		limiter = 0;
		vmlist.clear();
		moved.clear();
		success = true;
		adi = adj = -1;
		ref_i = -1;
		vmwp_ref = -1;
		cluster_cover = 0;
		swap_limit = 0;
	}
	void set_swap_limit(int set)
	{
		swap_limit = set;
	}
	string x(int x, int y)
	{
		string s;
		char xy[10000] = {0};
		sprintf(xy, "%d.%d.", x, y);
		s = xy;
		return s;
	}
	string x(int x, int y, int z, int w)
	{
		string s;
		char xyzw[20000] = {0};
		sprintf(xyzw, "%d.%d.%d.%d.", x, y, z, w);
		s = xyzw;
		return s;
	}
	bool construct(Routing_topo *tp, string hpath, string vpath)
	{
		topo = tp;
		FILE *hin = fopen(hpath.c_str(), "r");
		if (!hin)
		{
			cerr << "cannot open file!\n";
			exit(1);
		}
		int hnum;
		fscanf(hin, "%d", &hnum);
		int i;
		for (i = 0; i < hnum; i++)
		{
			int hn, slots;
			fscanf(hin, "%d%d", &hn, &slots);
			ishost[hn] = true;
			vHost newhost;
			newhost.host = hn;
			newhost.slots = slots;
			totalSlots += slots;
			hosts[hn] = newhost;
		}
		fclose(hin);
		FILE *vin = fopen(vpath.c_str(), "r");
		if (!vin)
		{
			cerr << "cannot open file!\n";
			exit(1);
		}
		int vnum, vpairnum;
		fscanf(vin, "%d%d", &vnum, &vpairnum);
		flow.resize(vnum);
		for (i = 0; i < vnum; i++)
		{
			VM newvm;
			newvm.num = i;
			vms[i] = newvm;
			flow[i].resize(vnum);
		}
		for (i = 0; i < vpairnum; i++)
		{
			int src, dst;
			double nflow = 0.0;
			fscanf(vin, "%d%d%lf", &src, &dst, &nflow);
			map<int, double>::iterator it = vms[src].flow.find(dst);
			if (it == vms[src].flow.end())
			{
				vms[src].flow[dst] = nflow;
				flow[src][dst] = nflow;
			}
			else
			{
				(*it).second += nflow;
				flow[src][dst] += nflow;
			}
		}
		fclose(vin);
		treeBuilt = false;
		return true;
	}
	bool vm_place(string path)
	{
		FILE *input = fopen(path.c_str(), "r");
		int total;
		fscanf(input, "%d", &total);
		int i;
		for (i = 0; i < total; i++)
		{
			int vm, host;
			fscanf(input, "%d%d", &vm, &host);
			place(vm, host);
		}
		fscanf(input, "%d %d %d", &preadi, &preadj, &vmwp_ref);
		fscanf(input, "%d", &ref_i);
		fclose(input);
		return true;
	}
	/*
	 * rand_perm pick n-permutation from 1..m
	*/
	bool rand_perm(int n, int m, int perm[])
	{
		srand(time(NULL));
		int tempPerm[maxVMsize] = {0};
		int i;
		for (i = 0; i < m; i++)
			tempPerm[i] = i;
		int range = m;
		int pos = 0;
		for (i = 0; i < n; i++)
		{
			pos = rand() % range;
			perm[i] = tempPerm[pos];
			tempPerm[pos] = tempPerm[range - 1];
			range--;
		}
		return true;
	}
	bool place(int vm, int host)
	{
		map<int, vHost>::iterator it;
		if ((it = hosts.find(host)) == hosts.end())
		{
			return false;
		}
		vms[vm].host = host;
		(*it).second.sptVms.push_back(vm);
		topo->place(vm, host);
		return true;
	}
	bool remove(int vm, int host)
	{
		map<int, vHost>::iterator it;
		list<int>::iterator lit;
		if ((it = hosts.find(host)) == hosts.end())
		{
			return false;
		}
		for (lit = (*it).second.sptVms.begin(); lit != (*it).second.sptVms.end(); lit++)
		{
			if ((*lit) == vm)
			{
				(*it).second.sptVms.erase(lit);
				vms[vm].host = 0;
				topo->remove(vm, host);
				return true;
			}
		}
		return false;
	}
	bool remove_all()
	{
		map<int, vHost>::iterator it;
		for (it = hosts.begin(); it != hosts.end(); it++)
		{
			(*it).second.sptVms.clear();
		}
		map<int, VM>::iterator vmit;
		for (vmit = vms.begin(); vmit != vms.end(); vmit++)
		{
			topo->remove((*vmit).second.num, (*vmit).second.host);
			(*vmit).second.host = 0;
		}
		return true;
	}
	bool vm_random_place()
	{
		//srand(time(NULL));
		int vmn = vms.size();
		int perm[maxVMsize] = {0};
		int i = 0;
		map<int, VM>::iterator it;
		for (it = vms.begin(); it != vms.end(); it++)
		{
			perm[i] = (*it).second.num;
			i++;
		}
		int slotPerm[maxVMsize] = {0};
		rand_perm(vmn, totalSlots, slotPerm);
		for (i = 0; i < vmn; i++)
			cout << slotPerm[i] << " ";
		cout << endl;
		map<int, vHost>::iterator jt;
		i = 0;
		int k = 0;
		for (jt = hosts.begin(); jt != hosts.end(); jt++)
		{
			if (vmn <= 0) break;
			int slots = (*jt).second.slots;
			//int slotuse = rand() % slots + 1; // 1-slots
			int j;
			for (j = 0; j < slots; j++)
			{
				for (k = 0; k < vmn; k++)
				{
					if (slotPerm[k] == i)
					{
						(*jt).second.sptVms.push_back(perm[k]);
						vms[perm[k]].host = (*jt).second.host;
					}
				}
				i++;
			}
		}
		return true;
	}
	/*
	 * pick_nearest picks the i and j in ptree[level],
	 * so that:
	 * if level == 0:
	 *   flow(VMi, VMj) + flow(VMj, VMi) is the maximum flow;
	 * if level > 0:
	 *   1/(i.size * j.size) * \sum_ x \in i, y \in j (flow(VMx, VMy) + flow(VMy, VMx))
	 *     is the maximum among all ptree[level]s.
	 * because:
	 *   for two sub clusters, our target is to place these
	 *   two as close as we can, if they communicate quite a
	 *   lot.
	*/
	double pick_nearest(vector<node*> leafnodes, int &ri, int &rj)
	{
		int i, j;
		ri = 0;
		rj = 1;
		double maxmum = 0;
		for (i = 0; i < leafnodes.size() - 1; i++)
		{
			for (j = i + 1; j < leafnodes.size(); j++)
			{
				int ki, kj;
				double sum = 0;
				for (ki = 0; ki < leafnodes[i]->cluster.size(); ki++)
					for(kj = 0; kj < leafnodes[j]->cluster.size(); kj++)
					{
						//string xy = x(leafnodes[i]->cluster[ki], leafnodes[j]->cluster[kj]);
						//string yx = x(leafnodes[j]->cluster[kj], leafnodes[i]->cluster[ki]);
						int x = leafnodes[i]->cluster[ki];
						int y = leafnodes[j]->cluster[kj];
						sum += flow[x][y] + flow[y][x];
					}
				sum /= leafnodes[i]->cluster.size() * leafnodes[j]->cluster.size();
				if (sum > maxmum)
				{
					ri = i;
					rj = j;
					maxmum = sum;
				}
			}
		}
		return maxmum;
	}
	/*
	 * establish the partition tree by bottom up method
	 * tree:
	 *  node vector<int>: set of symbols of vms in the childnodes
	 * i-partition:
	 *  subtrees in the depth of i
	*/
	int partitionTree()
	{
		i_partition = 0;
		ptree.clear();
		map<int, VM>::iterator it;
		ptree.resize(vms.size());
		for (it = vms.begin(); it != vms.end(); it++)
		{
			node *s = new node();
			s->cluster.clear();
			s->parent = NULL;
			s->cluster.push_back((*it).second.num);
			s->center = -1;
			ptree[0].push_back(s);//construct leaf
			s->n = ptree[0].size() - 1;
			leafvms[(*it).second.num] = s;
		}
		//vector<nodetype>::iterator i, j;
		int level = 0;
		while (ptree[level].size() > 1)// && level < this->swap_limit * 3)
		{
			int i, j;
			int iteri;
			nearest nr;
			nr.level = level + 1;
			nr.value = pick_nearest(ptree[level], i, j);
			if (i_max.size() <= 0)
			{
				
			}
			else
			{
				i_max[i_max.size() - 1].ratio = i_max[i_max.size() - 1].value - nr.value;
			}
			//cout << nr.value << " ";
			/*for (iteri = 0; iteri < ptree[level][i]->cluster.size(); iteri++)
			{
				focus[x(ptree[level][i]->cluster[iteri], level)] = true;
			}
			for (iteri = 0; iteri < ptree[level][j]->cluster.size(); iteri++)
			{
				focus[x(ptree[level][j]->cluster[iteri], level)] = true;
			}*/
			int leafi;
			for (leafi = 0; leafi < ptree[level].size(); leafi++)
			{
				if (leafi == i || leafi == j) continue;
				node *s = new node();
				s->parent = NULL;
				s->cluster = vector<int>();
				s->cluster = ptree[level][leafi]->cluster;
				s->center = -1;
				s->n = ptree[level + 1].size();
				ptree[level][leafi]->parent = s;
				ptree[level + 1].push_back(s);
			}
			int k;
			node *s = new node();
			s->cluster = vector<int>();
			s->parent = NULL;
			int isize = ptree[level][i]->cluster.size();
			int jsize = ptree[level][j]->cluster.size();
			ptree[level][i]->parent = s;
			ptree[level][j]->parent = s;
			s->cluster = ptree[level][i]->cluster;
			for (k = 0; k < jsize; k++)
			{
				if (s->cluster.size() <= k + isize) s->cluster.resize(k + isize + 1);
				s->cluster[k + isize] = ptree[level][j]->cluster[k];
			}
			s->min_aver = std::min(ptree[level][j]->min_aver, std::min(nr.value, ptree[level][i]->min_aver));
			s->center = -1;
			s->n = ptree[level + 1].size();
			ptree[level + 1].push_back(s);
			nr.leveli = ptree[level + 1].size() - 1;
			i_max.push_back(nr);
			level++;
		}
		treeBuilt = true;
		i_partition = (ptree.size() - 2);
		if (i_partition < 0) i_partition = 0;
		sort(i_max.begin(), i_max.end());
		reverse(i_max.begin(), i_max.end());
		int loop = 0;
		for (loop = 0; loop < i_max.size(); loop++)
		{
			i_focus[x(i_max[loop].level, i_max[loop].leveli)] = 0;
		}
		for (loop = 0; loop < i_max.size() && loop < swap_limit * 2; loop++)
		{
			int lev = i_max[loop].level;
			int lei = i_max[loop].leveli;
			i_focus[x(lev, lei)] = true;
			ipfocus[lev] = true;
			//if (ptree[lev][lei])i_focus[i_max[loop].level] = true;
		}
		//i_partition = ptree.size() - 2;
		return i_partition;
	}
	int inCluster(int i, int level)
	{
		node *nvm;
		nvm = leafvms[i];
		int lev = 0;
		while (lev < level)
		{
			nvm = nvm->parent;
			lev++;
		}
		return nvm->n;
	}
	bool inSameCluster(int i, int j, int i_part)
	{
		i_partition = i_part;
		if (i == j) return true;
		node *ni, *nj;
		ni = leafvms[i];
		nj = leafvms[j];
		int level = 0;
		while (level < i_part)
		{
			ni = ni->parent;
			nj = nj->parent;
			if (ni == nj) return true;
			level++;
		}
		return false;
	}
	double calculateClusterFlow(int vm, int i_part)
	{
		node *nvm = leafvms[vm];
		int level = 0;
		while(level < i_part)
		{
			nvm = nvm->parent;
			level++;
		}
		double sum = 0;
		double fsum = 0;
		int i;
		if (nvm->cluster.size() == 1) return 32767;
		for (i = 0; i < nvm->cluster.size(); i++)
		{
			if (nvm->cluster[i] == vm) continue;
			if (vms[vm].host == vms[nvm->cluster[i]].host) continue;
			//string vxy = x(vms[vm].num, vms[nvm->cluster[i]].num);
			//string vyx = x(vms[nvm->cluster[i]].num, vms[vm].num);
			int vx = vms[vm].num;
			int vy = vms[nvm->cluster[i]].num;
			//string xy = x(vms[vm].host, vms[nvm->cluster[i]].host);
			//string yx = x(vms[nvm->cluster[i]].host, vms[vm].host);
			int x = vms[vm].host;
			int y = vms[nvm ->cluster[i]].host;
			map<string, double>::iterator it;
			fsum += flow[vx][vy];
			fsum += flow[vy][vx];
			//cout << topo->distance[xy] << " ";
			sum += (flow[vx][vy] + flow[vy][vx]) * topo->distance[x][y];
		}
		sum /= fsum;
		//cout << "sum" << sum << " ";
		return sum;
	}
	/*double calculateClusterFlowOld(int vm, int i_part)
	{
		node *nvm = leafvms[vm];
		int level = 0;
		while(level < i_part)
		{
			nvm = nvm->parent;
			level++;
		}
		double sum = 0;
		double fsum = 0;
		int i;
		if (nvm->cluster.size() == 1) return 32767;
		for (i = 0; i < nvm->cluster.size(); i++)
		{
			if (nvm->cluster[i] == vm) continue;
			string xy = x(vms[vm].host, vms[nvm->cluster[i]].host);
			string yx = x(vms[nvm->cluster[i]].host, vms[vm].host);
			map<string, double>::iterator it;
			fsum += flow[xy];
			fsum += flow[yx];
			map<string, map<string, double> >::iterator st_it;
			st_it = topo->fijst.find(xy);
			if (st_it != topo->fijst.end())
			{
				for (it = (*st_it).second.begin(); it != (*st_it).second.end(); it++)
				{
					string ij = (*it).first;
					sum += (*it).second / topo->capacity[ij];//* utility[ij];	
				}
			}
			st_it = topo->fijst.find(yx);
			if (st_it != topo->fijst.end())
			{
				for (it = (*st_it).second.begin(); it != (*st_it).second.end(); it++)
				{
					string ij = (*it).first;
					sum += (*it).second / topo->capacity[ij];//* utility[ij];	
				}
			}
		}
		if (sum != 0) sum /= fsum;
		return sum;
	}*/
	bool isort()
	{
		int vsize = vmlist.size();
		clusterFlow.clear();
		clusterFlow.resize(vsize);
		int i;
		for (i = 0; i < vmlist.size(); i++)
		{
			clusterFlow[i] = calculateClusterFlow(vmlist[i], i_partition);
		}
		int j = 0;
		int itemp;
		double dtemp;
		for (i = 0; i < vmlist.size() - 1; i++)
			for (j = 0; j < vmlist.size() - i - 1; j++)
				if (clusterFlow[j] < clusterFlow[j + 1])
				{
					itemp = vmlist[j];
					vmlist[j] = vmlist[j + 1];
					vmlist[j + 1] = itemp;
					dtemp = clusterFlow[j];
					clusterFlow[j] = clusterFlow[j + 1];
					clusterFlow[j + 1] = dtemp;
				}
		return true;
	}
	bool calculateDistance()
	{
		distance.clear();
		//map<string, double>::iterator path_iter;
		int i, j;
		distance.resize(topo->nodes.size());
		for (i = 0; i < topo->nodes.size(); i++)
			distance[i].resize(topo->nodes.size());
		for (i = 0; i < topo->nodes.size(); i++)
			for (j = 0; j < topo->nodes.size(); j++)
			{
				distance[i][j] = hosts.size() / topo->distance[i][j];
			}
		for (i = 0; i < hosts.size(); i++)
		{
			distance[i][i] = 999;
		}
		return true;
	}
	/*
	 * adjust() adjusts vm placement due to fijst, flow
	 * and utility:
	 *   1) Calculate the clusterFlow:
	 *      Average utility per flow of a vm in its i-
	 *   cluster, the variable clusterFlow represents 
	 *   how convenient it is for a vm to communicate 
	 *   with its cluster neighboors;
	 *   2) Sort the vm list in descending sequence of
	 *   clusterFlow:
	 *      Vms at the beginning of the list are vms wh-
	 *   ich has a bad environment, while the latter 
	 *   ones are well-placed.
	 *   3) Check the first adjustFirstN vms to see whe-
	 *   ther there are ones share the same i-cluster 
	 *   with the last adjustLastN vms, pick them out.
	 *   If there are, goto 4); else i_partition++, go-
	 *   to 3):
	 *      Why not goto 1) after i_partition++?
	 *   A clusterFlow calculating is time consuming.
	 *   And what we need is how well they are placed.
	 *   4) Check from the beginning for vms in a diff-
	 *   erent cluster, while their distance to the la-
	 *   tter vm is less than limiter, swap this vm wi-
	 *   th the former one.
	*/
	int adjust(int &succ)
	{
		int vsize = vms.size();
		if (i_partition >= ptree.size() - 1) i_partition = ptree.size() - 2;
		while (!ipfocus[i_partition] && i_partition > 0)
		{
			std::cout << i_partition << endl;
			i_partition--;
		}
		if (i_partition <= 0) return false;
		vmlist.clear();
		vmlist.resize(vsize);
		int i = 0;
		map<int, VM>::iterator it;
		for (it = vms.begin(); it != vms.end(); it++)
		{
			vmlist[i] = (*it).second.num;
			i++;
		}
		srand(time(NULL));
		bool whiledo = true;
		isort();
		calculateDistance();
		cout << "Look for candidates\n";
		int vmwp = -1;
		{
			int vmi = 0;
			int vmj = 0;
			int j;
			bool flag = false;
			int positionj = 0;
			for (j = vmlist.size() - 1; j > 0; j--)
			{
				if (clusterFlow[j] == 32767)
				{
					continue;
				}
				//if (leafvms[i_partition]->center != -1)
				{
					//if (vmlist[j] != leafvms[i_partition]->center) continue;
				}
				if (centered[vmlist[j]]) continue;
				//if (!focus[x(i_partition, vmlist[j])]) continue;
				if (!i_focus[x(i_partition, inCluster(vmlist[j], i_partition))]) continue;
				//if (vmwp_ref != -1)
					//if(inSameCluster(vmlist[j], vmwp_ref, i_partition)) continue;
				for (i = 0; i < j; i++)
				{
					if (clusterFlow[i] == 32767)
					{
						continue;
					}
					if (inSameCluster(vmlist[i], vmlist[j], i_partition))
					{
						vmi = vmlist[i];
						vmwp = vmlist[j];
						positionj = j;
						//found
						int bestj;
						double bestDis = 0;
						bool foundj = false;
						bool exceed = false;
						int k;
						for (k = 0; k < vmlist.size() ; k++)
						{
							if (vmlist[k] == vmwp)
 							{
								exceed = true;
								break;
							}
							vmj = vmlist[k];
							if (vmi == vmj) continue;
							if (moved[x(vmi, vmj)])
							{
								continue;
							}
							double tempdistance = distance[vms[vmj].host][vms[vmwp].host];
							if (tempdistance > distance[vms[vmi].host][vms[vmwp].host]/*limiter*/ && !inSameCluster(vmj, vmwp, i_partition))
							{
								//swap i,j
								if (tempdistance > bestDis)
								{
									bestj = vmj;
									bestDis = tempdistance;
									foundj = true;
								}
							}
						}
						if (foundj)
						{
							vmj = bestj;
							int hosti = vms[vmi].host;
							int hostj = vms[vmj].host;
							remove(vmi, hosti);
							remove(vmj, hostj);
							place(vmi, hostj);
							place(vmj, hosti);
							whiledo = false;
							success = true;
							preadi = vmi;
							preadj = vmj;
							vmwp_ref = vmwp;
							moved[x(vmi, vmj)] = true;
							moved[x(vmj, vmi)] = true;
							flag = true;
							//cout << "new-vm swap" << i_partition << ": " << vmi << " " << vmj << " " << vmwp << endl;
							centered[vmwp_ref] = true;
							int levi;
							node *vmwp_node = leafvms[vmwp];
							for (levi = 0; levi <= i_partition; levi++)
							{
								vmwp_node->center = vmwp;
								vmwp_node = vmwp_node->parent;
							}
							succ++;
							break;
						}
					}
				}
				if (flag) break;
			}
		}
		if (!whiledo && vmwp_ref != -1)
		{
			//cout << "previous adjust center vmwp: " << vmwp_ref << endl;
			int vmi = 0;
			int vmj = 0;
			vmwp = vmwp_ref;
			int j;
			for (j = vmlist.size() - 1; j > 0 && vmlist[j] != vmwp; j--);
			for (i = 0; i < j; i++)
			{
				if (i == preadi || i == preadj) continue;
				if (clusterFlow[i] == 32767) continue;
				if (inSameCluster(vmlist[i], vmwp_ref, i_partition))
				{
					vmi = vmlist[i];
					int bestj;
					double bestDis = 0;
					bool foundj = false;
					bool exceed = false;
					int k;
					for (k = 0; k <= j ; k++)
					{
						if (vmlist[k] == vmwp)
 						{
							exceed = true;
							break;
						}
						vmj = vmlist[k];
						if (vmi == vmj) continue;
						if (moved[x(vmi, vmj)])
						{
							continue;
						}
						double tempdistance = distance[vms[vmj].host][vms[vmwp].host];
						if (tempdistance > distance[vms[vmi].host][vms[vmwp].host]/*limiter*/ && !inSameCluster(vmj, vmwp, i_partition))
						{
							//swap i,j
							if (tempdistance > bestDis)
							{
								bestj = vmj;
								bestDis = tempdistance;
								foundj = true;
							}
						}
					}
					if (foundj)
					{
						vmj = bestj;
						int hosti = vms[vmi].host;
						int hostj = vms[vmj].host;
						remove(vmi, hosti);
						remove(vmj, hostj);
						place(vmi, hostj);
						place(vmj, hosti);
						whiledo = false;
						success = true;
						preadi = vmi;
						preadj = vmj;
						moved[x(vmi, vmj)] = true;
						moved[x(vmj, vmi)] = true;
						succ++;
						//cout << "pre-vm swap" << i_partition << ": " << vmi << " " << vmj << " " << vmwp << endl;
					}
				}
			}
		}
		cluster_cover++;
		if (whiledo || cluster_cover >= 2)
		{
			i_partition--;
			vmwp_ref = -1;
			cluster_cover = 0;
			centered.clear();
			moved.clear();
		}
		if (i_partition < 0) return -1;
		else return i_partition;
	}
	bool output()
	{
		cout << "Final Placement: \n";
		map<int, VM>::iterator it;
		for (it = vms.begin(); it != vms.end(); it++)
		{
			printf("%d %d\n", (*it).second.num, (*it).second.host);
		}
		return true;
	}
	bool output_vm(string path)
	{
		FILE *fout = fopen(path.c_str(), "w");
		fprintf(fout, "%d\n", vms.size());
		map<int, VM>::iterator it;
		for (it = vms.begin(); it != vms.end(); it++)
		{
			fprintf(fout, "%d %d\n", (*it).second.num, (*it).second.host);
		}
		fclose(fout);
		return true;
	}
	bool clear()
	{
		vms.clear();
		hosts.clear();
		flow.clear();
		ishost.clear();
		leafvms.clear();
		utility.clear();
		vmlist.clear();
		topo = NULL;
		totalSlots = 0;
		treeBuilt = false;
		i_partition = -1;
		limiter = 0;
		vmlist.clear();
		success = true;
		adi = adj = -1;
		ref_i = -1;
		vmwp_ref = -1;
		return true;
	}
	bool put_to_topology()
	{
		topo->rt_construct(vms);
		return true;
	}
	bool route()
	{
		cout << "simple ospf route...\n";
		topo->simple_ospf_route();
		/*map<string, double>::iterator dit;
		for (dit = topo->distance.begin(); dit != topo->distance.end(); dit++)
			cout << (*dit).first << " " << (*dit).second << endl;*/
		//cout << "calculating utility...\n";
		//topo->utility_calculate();
		return true;
	}
	bool check_route()
	{
		cout << "distribute ospf route...\n";
		topo->distribute_ospf_route();
		cout << "calculating utility...\n";
		topo->utility_calculate();
		return true;
	}
};

#endif